﻿#include "BinaryTreeBasicHandler.h"
#include "Queue.h"

// 基础操作函数
// 创建节点
TreeNode* CreateNode(DataType val)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	if (node == NULL)
	{
		perror("malloc new node error!\n");
		return NULL;
	}
	node->val = val;
	node->left = node->right = NULL;
	return node;
}

// 二叉树 - 直接构造
TreeNode* CreateDisplayBinaryTree()
{
	TreeNode* A = CreateNode('A');
	TreeNode* B = CreateNode('B');
	TreeNode* C = CreateNode('C');
	TreeNode* D = CreateNode('D');
	TreeNode* E = CreateNode('E');
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	return A;
}

// 二叉树 - 通过前序遍历序列构造 eg：ABD##E#H##CF##G##
TreeNode* CreateBinaryTreeByPreOrderString(DataType* str, int* i)
{
	if (str[*i] == '#') return NULL;
	TreeNode* node = CreateNode(str[*i]);
	++(*i);
	node->left = CreateBinaryTreeByPreOrderString(str, i);
	++(*i);
	node->right = CreateBinaryTreeByPreOrderString(str, i);
	return node;
}

// 二叉树 - 销毁
void DestoryBinaryTree(TreeNode* root)
{
	if (root == NULL) return;
	DestoryBinaryTree(root->left);
	DestoryBinaryTree(root->right);
	free(root);
}

// 二叉树 - 节点个数
int BinaryTreeSize(TreeNode* root)
{
	if (root == NULL) return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

// 二叉树 - 叶子节点个数
int BinaryTreeLeafSize(TreeNode* root)
{
	if (root == NULL) return 0;
	if (root->left == NULL && root->right == NULL) return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// 二叉树 - 第k层节点个数
int BinaryTreeKLevelSize(TreeNode* root, int k)
{
	if (k == 0 || root == NULL) return 0;
	if (k == 1) return 1;
	return BinaryTreeKLevelSize(root->left, k - 1) + BinaryTreeKLevelSize(root->right, k - 1);
}

// 二叉树 - 查找值为val的节点
TreeNode* BinaryTreeFind(TreeNode* root, DataType val)
{
	if (root == NULL) return NULL;
	if (root->val == val) return root;
	TreeNode* left = BinaryTreeFind(root->left, val);
	if (left) return left;
	TreeNode* right = BinaryTreeFind(root->right, val);
	if (right) return right;
	return NULL;
}

// 二叉树 - 判断是否为完全二叉树 是为1 不是为0
int BinaryTreeComplete(TreeNode* root)
{
	if (root == NULL) return 1;
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue, root);
	int haveChild = 0;
	while (!QueueEmpty(&queue))
	{
		int sz = QueueSize(&queue);
		TreeNode* node = NULL;
		haveChild = 0;

		while (sz--)
		{
			node = QueueFront(&queue);
			QueuePop(&queue);
			if (node && (node->left != NULL || node->right != NULL))
			{
				haveChild = 1;
			}
			if (node == NULL)
			{
				break;
			}
			QueuePush(&queue, node->left);
			QueuePush(&queue, node->right);
		}

		if (node == NULL)
		{
			break;
		}
	}

	if (haveChild == 1)
	{
		return 0;
	}

	while (!QueueEmpty(&queue))
	{
		TreeNode* node = QueueFront(&queue);
		QueuePop(&queue);
		if (node != NULL)
		{
			return 0;
		}
	}
	return 1;
}

// 遍历操作函数 - 递归方式
// 前序遍历
void PreOrderByRecursion(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->val);
	PreOrderByRecursion(root->left);
	PreOrderByRecursion(root->right);
}

// 中序遍历
void MidOrderByRecursion(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	MidOrderByRecursion(root->left);
	printf("%c ", root->val);
	MidOrderByRecursion(root->right);
}

// 后序遍历
void PostOrderByRecursion(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrderByRecursion(root->left);
	PostOrderByRecursion(root->right);
	printf("%c ", root->val);
}

// 遍历操作函数 - 层序
void LevelOrder(TreeNode* root)
{
	if (root == NULL) return;
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue, root);
	while (!QueueEmpty(&queue))
	{
		int sz = QueueSize(&queue);
		while (sz--)
		{
			TreeNode* node = QueueFront(&queue);
			QueuePop(&queue);
			printf("%c ", node->val);
			if (node->left != NULL)
			{
				QueuePush(&queue, node->left);
			}
			if (node->right != NULL)
			{
				QueuePush(&queue, node->right);
			}
		}
		printf("\n");
	}
}